package heap;

import java.util.*;

/**
 * Creared with IntelliJ IDEA.
 * Description:
 * User:yxd
 * Date:2022-01-22
 * Time:14:12
 */
public class Main {
    public static void main(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] array = {5,13,27,3,28,77,15};
        testHeap.createHeap(array);
        testHeap.offer(24);
        System.out.println(testHeap.poll());
        testHeap.offer(99);
        System.out.println(testHeap.poll());
        System.out.println(testHeap.peek());
        testHeap.heapSort();
        System.out.println("=========");
        System.out.println(Arrays.toString(topK(array,3)));
        int[] a ={1,7,11};
        int[] b ={2,4,6};
        List<List<Integer>> tmp = kSmallestPairs(a,b,3);
        System.out.println(tmp);
        /*大根堆的创建方式
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override//比较器
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
                                                                  lambda表达式：但可读性差
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((x,y)->{return y - x;});
        */

    }
    public static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {

        PriorityQueue<List<Integer>> maxHeap = new PriorityQueue<>(k, new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return (o2.get(0)+o2.get(1))-(o1.get(0)+o1.get(1));
            }
        });//先以大根堆的形式创建一个堆
        for(int i = 0;i < Math.min(k, nums1.length); i++){
            for (int j = 0; j < Math.min(k, nums2.length); j++) {
                //以topK的方法来做 求前k小的数需要先创建一个k大小的大根堆，然后把后面所有元素入堆，
                // 小于堆顶的就先把堆顶的最大值出队再放入较小的值，有可能这个就是前面k个最小的值之一，
                // 最后堆里面的值就是前k个最小的值堆顶是第k小的值
                //要求前k个最大值也是一样的做法，只不过创建小根堆就可以
                if(maxHeap.size() < k){
                    List<Integer> ret = new ArrayList<>();
                    ret.add(nums1[i]);
                    ret.add(nums2[j]);
                    maxHeap.offer(ret);
                }else{
                    int top = maxHeap.peek().get(0) + maxHeap.peek().get(1);//获取栈顶元素
                    if(top > nums1[i] + nums2[j]){//比较哪个更小，后面的值更小就入堆
                        maxHeap.poll();
                        List<Integer> ret = new ArrayList<>();
                        ret.add(nums1[i]);
                        ret.add(nums2[j]);
                        maxHeap.offer(ret);
                    }
                }
            }
        }
        List<List<Integer>> tmp = new ArrayList<>();
        for (int i = 0; i < k && !maxHeap.isEmpty(); i++) {
            tmp.add(maxHeap.poll());
        }
        return tmp;
    }
    //前k个小的数
    public static  int[] topK(int[] array,int k){
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer o1,Integer o2){
                return o2 - o1;
            }
        });
        for (int i = 0; i < array.length; i++) {
            if(priorityQueue.size() < k){
                priorityQueue.offer(array[i]);
            }else{
                int top = priorityQueue.peek();
                if(top > array[i]){
                    priorityQueue.poll();
                    priorityQueue.offer(array[i]);
                }
            }
        }
        int[] tmp = new int[k];
        for (int i = 0; i < tmp.length; i++) {
            tmp[i] = priorityQueue.poll();
        }
        return tmp;

    }
}
